package com.kizuki.algorithm.sort;

import java.util.Arrays;

public class Sort {

    // 快排
    // 优化随机选一个基准值 三数中值
    public void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int key = arr[start];
        int left = start;
        int right = end;
        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            if (left < right) {
                arr[left++] = arr[right];
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        arr[left] = key;
        quickSort(arr, start, left - 1);
        quickSort(arr, left + 1, end);
    }

    // 链表排序也是用归并排序的思想，找中间位置用快慢指针
    // 归并排序
    public void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);
            merge(arr, temp, left, mid, right);
        }
    }

    public void merge(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = i;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k] = arr[i++];
            } else {
                temp[k] = arr[j++];
            }
            k++;
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (int l = left; l <= right; l++) {
            arr[l] = temp[l];
        }
    }

    // 冒泡排序
    public void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j + 1 < len - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }


    // 一个节点为i，其父亲为i/2，左子树i*2+1，右子树i*2+2
    //堆排序
    public void heapSort(int[] arr) {
        int len = arr.length;
        for (int i = len / 2; i >= 0; i --) { // 生成大顶堆
            adjustHeap(arr, i, len);
        }
        for (int i = len - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;  // 修改之后只有0位置上是不满足大顶堆的
            adjustHeap(arr, 0, i);
        }

    }

    // 将数组 i到len-1 调整为大顶堆
    public void adjustHeap(int[] arr, int i, int len){
        for (int child; leftChild(i) < len; i = child) {
            child = leftChild(i);
            if (child + 1 < len && arr[child] < arr[child + 1]) {
                child += 1;
            }
            if (arr[child] > arr[i]) {
                int temp = arr[child];
                arr[child] = arr[i];
                arr[i] = temp;
            } else {
                break;
            }
        }
    }

    public int leftChild(int i) {
        return 2 * i + 1;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{14, 5, 42, 8, 22, 1, 9, 2, 3, 10};
        printArray(arr, "初始数组");
        int length = arr.length;
        Sort sort = new Sort();

        int[] a1 = getCopyArray(arr);
        sort.quickSort(a1, 0, length - 1);
        printArray(a1, "快排");

        int[] a2 = getCopyArray(arr);
        sort.mergeSort(a2, new int[length], 0, length - 1);
        printArray(a2, "归并排序");

        int[] a3 = getCopyArray(arr);
        sort.bubbleSort(a3);
        printArray(a3, "冒泡排序");

        int[] a4 = getCopyArray(arr);
        sort.heapSort(a4);
        printArray(a4, "堆排序");

    }

    public static int[] getCopyArray(int[] arr) {
        return Arrays.copyOf(arr, arr.length);
    }

    public static void printArray(int[] arr, String pre) {
        if (pre != null) {
            System.out.println(pre);
        }
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }


}
